#include <stdio.h>
//线性表之顺序表（正常初始化——>栈区）
//内容：初始化，插入，打印(遍历)，删除，查找
#define MAXSIZE 100  //定义顺序表足够大的长度(可能达到的最大长度)
typedef int ElemType; //这样为了方便修改输入数据的类型：比如，想都改为输入浮点数，那么就将int改成double即可
//1️⃣结构体的声明：顺序表的首地址+长度
typedef struct    //结构体标签省略
{
    //通常用数组来描述数据结构中的顺序存储结构，即顺序表
    ElemType data[MAXSIZE]; //data数组名，存储顺序表(数组)的首地址
    int length;  //存储顺序表的长度
}Sqlist; //类型重命名，结构体的别名，顺序表本身的结构类型是结构体(struct+标签)，而重命名后顺序表结构类型为Sqlist
//2️⃣初始化
void Initlist(Sqlist *ps)
{ 
    //data是指针常量，不用初始化
    ps->length=0;  //顺序表长度为0
}
//3️⃣插入
int addlist(Sqlist *ps,ElemType n)
{
    if(ps->length>=MAXSIZE)
    {
        printf("顺序表已满\n");
        return 0;
    }
    ps->data[ps->length]=n;
    ps->length++; //插入完顺序表长度+1，但已插入的数据下标为此时的length-1
    return 1;
}
//4️⃣打印（遍历）
void printlist(Sqlist *ps)
{
    int i;
    for(i=0;i<ps->length;i++)
    {
        printf("%d ",ps->data[i]);
    }
    printf("\n");
}
//5️⃣插入：在顺序表中任意位置插入
//思路：第m个元素下标为m-1，他后面第一个元素的下标为m，从m-1到length-1都向后移动
//从length-1开始向后覆盖，直到m-1覆盖m，再将n存到m-1的位置上
void charu(Sqlist *ps,int m,ElemType n)
{
    if(m-1<ps->length)
    {
        int i;
        for(i=ps->length-1;i>=m-1;i--)
        {
            ps->data[i+1]=ps->data[i];
        }
        ps->data[m-1]=n;
        ps->length++; //顺序表长度+1
    }
    else
    printf("位置不合理\n");
}
//最坏时间复杂度：O(n) 插入到第一个元素，后面n个元素都要向后移
//最好时间复杂度：O(1) 插入到最后一个元素，只有最后一个元素要向后移
//6️⃣第二种查找
int findlist(Sqlist *ps,ElemType i)
{
    int k;
    for(k=0;k<ps->length;k++)
    {
        if(ps->data[k]==i)
        {
            return k+1;
        }
    }
    if(k==ps->length)
    {
        return -1;
    }
}
//7️⃣删除
//思路：第c个数的下标是c-1，后面第一个元素下标为c，从c到length-1都向前移，然后length-1
void deletelist(Sqlist *ps,int c)
{
    if(c-1<ps->length)
    {
        int i;
        for(i=c;i<ps->length;i++)
        {
            ps->data[i-1]=ps->data[i];
        }
        ps->length--;
    }
    else
    {
        printf("位置不合理\n");
    }
}
int main()
{
    Sqlist s;//结构体变量的创建，也就是顺序表的创建
    //初始化
    Initlist(&s);
    printf("%zu\n",sizeof(s.data));//输出：400  顺序表所占内存大小为400字节
    //插入:因为创建时只有首地址和长度，所以存放数据时要一个一个插入进去，相当于赋值
    addlist(&s,22);
    addlist(&s,52);
    addlist(&s,66);
    addlist(&s,88);
    //打印
    printlist(&s);
    //插入：在顺序表中任意位置插入
    int m,n; //将n插到第m个元素那
    scanf("%d %d",&m,&n);
    charu(&s,m,n);
    //打印
    printlist(&s);
    //第一种查找：查找顺序表中第a个元素是什么
    int a;
    scanf("%d",&a);
    printf("%d\n",s.data[a-1]);
    //第二种查找：某个数在第ret个位置，是第ret个元素
    ElemType i;
    scanf("%d",&i);
    int ret=findlist(&s,i);
    if(ret!=-1)
    {
        printf("是第%d个元素\n",ret);
    }
    else
    {
        printf("顺序表中没有该数据\n");
    }
    //删除：删除第c个元素
    int c;
    scanf("%d",&c);
    deletelist(&s,c);
    //打印
    printlist(&s);
    return 0;
}
